When n balls are independently and uniformly tossed into n bins, the expected max-load—the number of balls in the heaviest bin—is (1+o(1))(logn/loglogn). This classical result plays a central role in the analysis of hashing with chaining and load balancing. However, implementing a truly random hash function is often impractical due to its high computational and storage costs.

In this talk, I will present recent work showing that hashing n balls into n bins via a random matrix over F2 achieves the same expected max-load of (1+o(1))(logn/loglogn). This strongly resolves an open question posed by Alon, Dietzfelbinger, Miltersen, Petrank, and Tardos, who had only asked whether the expected max-load was O(logn/loglogn).

Based on joint work with Michael Jaber and David Zuckerman.